"""
执行用时：
136 ms, 在所有 Python 提交中击败了38.46%的用户
内存消耗：
17.4 MB, 在所有 Python 提交中击败了82.05%的用户

其实这个问题的核心在于判断图中有没有奇数长度的环。本代码中还给出了环的长度，其实未必有必要。（仍可以进行优化）
"""

class Solution(object):
    def __init__(self):
        self.neighbors = None
        self.group = None
        self.arrive = None
        self.final_res = True

    def possibleBipartition(self, n, dislikes):
        """
        :type n: int
        :type dislikes: List[List[int]]
        :rtype: bool
        """
        self.final_res = True
        neighbors = [[] for _ in range(n)]
        for a, b in dislikes:
            neighbors[a - 1].append(b - 1)
            neighbors[b - 1].append(a - 1)
        self.neighbors = neighbors
        self.arrive = [False] * n
        self.group = [0] * n
        while not all(self.arrive):
            for i, a in enumerate(self.arrive):
                if not a:
                    self._part(i, 0)
        return self.final_res

    def _part(self, index, g):
        if self.arrive[index]:
            if (self.group[index] % 2) != g % 2:
                self.final_res = False
                return False
            return True
        self.arrive[index] = True
        self.group[index] = g

        for n in self.neighbors[index]:
            if not self._part(n, g + 1):
                return False
        return True


if __name__ == '__main__':
    s = Solution()
    print(s.possibleBipartition(n=4, dislikes=[[1, 2], [1, 3], [2, 4]]))
    print(s.possibleBipartition(n=3, dislikes=[[1, 2], [1, 3], [2, 3]]))
    print(s.possibleBipartition(n=5, dislikes=[[1, 2], [2, 3], [3, 4], [4, 5], [1, 5]]))

    print(s.possibleBipartition(n=5, dislikes=[[1, 2], [3, 4], [4, 5], [3, 5]]))
